# LeetCode 174、地下城游戏

# 一、题目描述

一些恶魔抓住了公主（P）并将她关在了地下城的右下角。地下城是由 M x N 个房间组成的二维网格。我们英勇的骑士（K）最初被安置在左上角的房间里，他必须穿过地下城并通过对抗恶魔来拯救公主。

骑士的初始健康点数为一个正整数。如果他的健康点数在某一时刻降至 0 或以下，他会立即死亡。

有些房间由恶魔守卫，因此骑士在进入这些房间时会失去健康点数（若房间里的值为负整数，则表示骑士将损失健康点数）；其他房间要么是空的（房间里的值为 0），要么包含增加骑士健康点数的魔法球（若房间里的值为正整数，则表示骑士将增加健康点数）。

为了尽快到达公主，骑士决定每次只向右或向下移动一步。

编写一个函数来计算确保骑士能够拯救到公主所需的最低初始健康点数。

例如，考虑到如下布局的地下城，如果骑士遵循最佳路径 右 -> 右 -> 下 -> 下，则骑士的初始健康点数至少为 7。

-2 (K)	-3	3
-5	-10	1
10	30	-5 (P)

说明:

骑士的健康点数没有上限。
任何房间都可能对骑士的健康点数造成威胁，也可能增加骑士的健康点数，包括骑士进入的左上角房间以及公主被监禁的右下角房间。

# 二、题目解析

# 三、参考代码

# 1、Java 代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 地下城游戏（ LeetCode 174 ）：https://leetcode-cn.com/problems/dungeon-game/
class Solution {
    public int calculateMinimumHP(int[][] dungeon) {

        // m 表示有多少行
        int m = dungeon.length;

        // n 表示每一行有多少个元素，即 n 表示有多少列
        int n = dungeon[0].length;

        // 保存每个位置的最小生命值
        // dp[0][0] 表示骑士来到第 0 行第 0 列时必须拥有的最小生命值
        // dp[0][i] 表示骑士来到第 0 行第 i 列时必须拥有的最小生命值
        // dp[j][0] 表示骑士来到第 j 行第 0 列时必须拥有的最小生命值
        // dp[i][j] 表示骑士来到第 i 行第 j 列时必须拥有的最小生命值
        int[][] dp = new int[m][n];

        // 先计算最右下角的值，因为骑士必须到达最右下角才能拯救公主
        // 最右下角的值有可能是 0 、正数、负数
        // 如果为 0 或者 正数，那么骑士到达这个位置之前只需要拥有最低存活的生命值 1 滴血即可
        // 如果为 负数，那么会在这个位置损失生命值，为了能够继续往后面走，那么必须至少拥有能够抵抗损耗的生命值
        // 比如，负数为 -5，那么必须至少拥有 6 点血，才足够损耗后还拥有最低存活的生命值 1 滴血
        // 所以，骑士在这个位置的血量要么是 1 ，要么是 （1 - 负数） ，比如  （ 1 - （-5）） = 6
        dp[ m - 1 ][ n - 1 ] = Math.max( 1 , 1 - dungeon[ m - 1 ][ n - 1 ]);

        // 当骑士来到最后一列的时候，他只能向下移动
        for( int i = m - 2 ; i >= 0 ; i-- ){

            // dp[1][0] + dungeon[1][0] >= dp[2][0]
            // 1、dp[1][0] >= dp[2][0] - dungeon[1][0]
            // 2、dp[1][0] >= 1
            // dp[1][0] = Math.max( 1,dp[2][0] - dungeon[1][0])

            dp[ i ][ n - 1 ] = Math.max( 1 , dp[ i + 1 ][ n - 1 ] - dungeon[ i ][ n - 1 ]);
        }


        // 当骑士来到最后一行的时候，他只能向右移动
        for( int j = n - 2 ; j >= 0 ; j-- ){

            // dp[1][0] + dungeon[1][0] >= dp[2][0]
            // 1、dp[1][0] >= dp[2][0] - dungeon[1][0]
            // 2、dp[1][0] >= 1
            // dp[1][0] = Math.max( 1,dp[2][0] - dungeon[1][0])

            dp[ m - 1][ j ] = Math.max( 1 , dp[ m - 1][ j + 1 ] - dungeon[ m - 1 ][ j ]);
        }
       
        
        // 从右下角开始向左上角推导
        // 相当于公主救骑士
        for( int i = m - 2 ; i >= 0 ; i--){

            for( int j = n - 2 ; j >= 0 ; j--){
                
                // 当骑士来到 （ i ，j ） 这个位置时，可以选择向右移动，也可以选择向下移动
                // 骑士会选择对血量要求少的那个方向
                int min = Math.min(dp[ i + 1 ][ j ] , dp[ i ][ j + 1 ]);

                // dp[1][0] + dungeon[1][0] >= dp[2][0]
                // 1、dp[1][0] >= dp[2][0] - dungeon[1][0]
                // 2、dp[1][0] >= 1
                // dp[1][0] = Math.max( 1,dp[2][0] - dungeon[1][0])
                dp[i][j] = Math.max( 1 , min - dungeon[i][j]);

            }
        }

        // dp[0][0] 表示骑士来到第 0 行第 0 列时必须拥有的最小生命值
        return dp[0][0];
    }
}

# 1、Java 代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 地下城游戏（ LeetCode 174 ）：https://leetcode-cn.com/problems/dungeon-game/
class Solution {
    public int calculateMinimumHP(int[][] dungeon) {

        // m 表示有多少行
        int m = dungeon.length;

        // n 表示每一行有多少个元素，即 n 表示有多少列
        int n = dungeon[0].length;

        // 保存每个位置的最小生命值
        // dp[0][0] 表示骑士来到第 0 行第 0 列时必须拥有的最小生命值
        // dp[0][i] 表示骑士来到第 0 行第 i 列时必须拥有的最小生命值
        // dp[j][0] 表示骑士来到第 j 行第 0 列时必须拥有的最小生命值
        // dp[i][j] 表示骑士来到第 i 行第 j 列时必须拥有的最小生命值
        int[][] dp = new int[m][n];

        // 先计算最右下角的值，因为骑士必须到达最右下角才能拯救公主
        // 最右下角的值有可能是 0 、正数、负数
        // 如果为 0 或者 正数，那么骑士到达这个位置之前只需要拥有最低存活的生命值 1 滴血即可
        // 如果为 负数，那么会在这个位置损失生命值，为了能够继续往后面走，那么必须至少拥有能够抵抗损耗的生命值
        // 比如，负数为 -5，那么必须至少拥有 6 点血，才足够损耗后还拥有最低存活的生命值 1 滴血
        // 所以，骑士在这个位置的血量要么是 1 ，要么是 （1 - 负数） ，比如  （ 1 - （-5）） = 6
        if( dungeon[ m - 1 ][ n - 1 ] >= 0  ){
            dp[ m - 1 ][ n - 1 ] = 1;
        }else{
            dp[ m - 1 ][ n - 1 ] = 1 - dungeon[ m - 1 ][ n - 1 ];
        }

        // 当骑士来到最后一列的时候，他只能向下移动
        for( int i = m - 2 ; i >= 0 ; i-- ){

            // dp[1][0] + dungeon[1][0] >= dp[2][0]
            // 1、dp[1][0] >= dp[2][0] - dungeon[1][0]
            // 2、dp[1][0] >= 1
            // dp[1][0] = Math.max( 1,dp[2][0] - dungeon[1][0])

            dp[ i ][ n - 1 ] = Math.max( 1 , dp[ i + 1 ][ n - 1 ] - dungeon[ i ][ n - 1 ]);
        }


        // 当骑士来到最后一行的时候，他只能向右移动
        for( int j = n - 2 ; j >= 0 ; j-- ){

            // dp[1][0] + dungeon[1][0] >= dp[2][0]
            // 1、dp[1][0] >= dp[2][0] - dungeon[1][0]
            // 2、dp[1][0] >= 1
            // dp[1][0] = Math.max( 1,dp[2][0] - dungeon[1][0])

            dp[ m - 1][ j ] = Math.max( 1 , dp[ m - 1][ j + 1 ] - dungeon[ m - 1 ][ j ]);
        }
       
        
        // 从右下角开始向左上角推导
        // 相当于公主救骑士
        for( int i = m - 2 ; i >= 0 ; i--){

            for( int j = n - 2 ; j >= 0 ; j--){
                
                // 当骑士来到 （ i ，j ） 这个位置时，可以选择向右移动，也可以选择向下移动
                // 骑士会选择对血量要求少的那个方向
                int min = Math.min(dp[ i + 1 ][ j ] , dp[ i ][ j + 1 ]);

                // dp[1][0] + dungeon[1][0] >= dp[2][0]
                // 1、dp[1][0] >= dp[2][0] - dungeon[1][0]
                // 2、dp[1][0] >= 1
                // dp[1][0] = Math.max( 1,dp[2][0] - dungeon[1][0])
                dp[i][j] = Math.max( 1 , min - dungeon[i][j]);

            }
        }

        // dp[0][0] 表示骑士来到第 0 行第 0 列时必须拥有的最小生命值
        return dp[0][0];
    }
}

# 2、C++ 代码

class Solution {
public:
    int calculateMinimumHP(vector<vector<int>>& dungeon) {

         // m 表示有多少行
        int m = dungeon.size();

        // n 表示每一行有多少个元素，即 n 表示有多少列
        int n = dungeon[0].size();

        // 保存每个位置的最小生命值
        // dp[0][0] 表示骑士来到第 0 行第 0 列时必须拥有的最小生命值
        // dp[0][i] 表示骑士来到第 0 行第 i 列时必须拥有的最小生命值
        // dp[j][0] 表示骑士来到第 j 行第 0 列时必须拥有的最小生命值
        // dp[i][j] 表示骑士来到第 i 行第 j 列时必须拥有的最小生命值
         auto dp = vector < vector < int>> ( m ,vector<int> (n));

        // 先计算最右下角的值，因为骑士必须到达最右下角才能拯救公主
        // 最右下角的值有可能是 0 、正数、负数
        // 如果为 0 或者 正数，那么骑士到达这个位置之前只需要拥有最低存活的生命值 1 滴血即可
        // 如果为 负数，那么会在这个位置损失生命值，为了能够继续往后面走，那么必须至少拥有能够抵抗损耗的生命值
        // 比如，负数为 -5，那么必须至少拥有 6 点血，才足够损耗后还拥有最低存活的生命值 1 滴血
        // 所以，骑士在这个位置的血量要么是 1 ，要么是 （1 - 负数） ，比如  （ 1 - （-5）） = 6
        if( dungeon[ m - 1 ][ n - 1 ] >= 0  ){
            dp[ m - 1 ][ n - 1 ] = 1;
        }else{
            dp[ m - 1 ][ n - 1 ] = 1 - dungeon[ m - 1 ][ n - 1 ];
        }

        // 当骑士来到最后一列的时候，他只能向下移动
        for( int i = m - 2 ; i >= 0 ; i-- ){

            // dp[1][0] + dungeon[1][0] >= dp[2][0]
            // 1、dp[1][0] >= dp[2][0] - dungeon[1][0]
            // 2、dp[1][0] >= 1
            // dp[1][0] = Math.max( 1,dp[2][0] - dungeon[1][0])

            dp[ i ][ n - 1 ] = max( 1 , dp[ i + 1 ][ n - 1 ] - dungeon[ i ][ n - 1 ]);
        }


        // 当骑士来到最后一行的时候，他只能向右移动
        for( int j = n - 2 ; j >= 0 ; j-- ){

            // dp[1][0] + dungeon[1][0] >= dp[2][0]
            // 1、dp[1][0] >= dp[2][0] - dungeon[1][0]
            // 2、dp[1][0] >= 1
            // dp[1][0] = Math.max( 1,dp[2][0] - dungeon[1][0])

            dp[ m - 1][ j ] = max( 1 , dp[ m - 1][ j + 1 ] - dungeon[ m - 1 ][ j ]);
        }
       
        
        // 从右下角开始向左上角推导
        // 相当于公主救骑士
        for( int i = m - 2 ; i >= 0 ; i--){

            for( int j = n - 2 ; j >= 0 ; j--){
                
                // 当骑士来到 （ i ，j ） 这个位置时，可以选择向右移动，也可以选择向下移动
                // 骑士会选择对血量要求少的那个方向
                int mmin = min(dp[ i + 1 ][ j ] , dp[ i ][ j + 1 ]);

                // dp[1][0] + dungeon[1][0] >= dp[2][0]
                // 1、dp[1][0] >= dp[2][0] - dungeon[1][0]
                // 2、dp[1][0] >= 1
                // dp[1][0] = Math.max( 1,dp[2][0] - dungeon[1][0])
                dp[i][j] = max( 1 , mmin - dungeon[i][j]);

            }
        }

        // dp[0][0] 表示骑士来到第 0 行第 0 列时必须拥有的最小生命值
        return dp[0][0];

    }
};

# 3、Python 代码

class Solution:
    def calculateMinimumHP(self, dungeon: List[List[int]]) -> int:
        # m 表示有多少行
        m = len(dungeon)

        # n 表示每一行有多少个元素，即 n 表示有多少列
        n = len(dungeon[0])

        # 保存每个位置的最小生命值
        # dp[0][0] 表示骑士来到第 0 行第 0 列时必须拥有的最小生命值
        # dp[0][i] 表示骑士来到第 0 行第 i 列时必须拥有的最小生命值
        # dp[j][0] 表示骑士来到第 j 行第 0 列时必须拥有的最小生命值
        # dp[i][j] 表示骑士来到第 i 行第 j 列时必须拥有的最小生命值
        dp = [[0] * n for _ in range(m)]

        # 先计算最右下角的值，因为骑士必须到达最右下角才能拯救公主
        # 最右下角的值有可能是 0 、正数、负数
        # 如果为 0 或者 正数，那么骑士到达这个位置之前只需要拥有最低存活的生命值 1 滴血即可
        # 如果为 负数，那么会在这个位置损失生命值，为了能够继续往后面走，那么必须至少拥有能够抵抗损耗的生命值
        # 比如，负数为 -5，那么必须至少拥有 6 点血，才足够损耗后还拥有最低存活的生命值 1 滴血
        # 所以，骑士在这个位置的血量要么是 1 ，要么是 （1 - 负数） ，比如  （ 1 - （-5）） = 6
        if dungeon[ m - 1 ][ n - 1 ] >= 0  : 
            dp[ m - 1 ][ n - 1 ] = 1
        else:
            dp[ m - 1 ][ n - 1 ] = 1 - dungeon[ m - 1 ][ n - 1 ]
        

        # 当骑士来到最后一列的时候，他只能向下移动
        for i in range( m - 2 , -1 ,-1 ) : 

            # dp[1][0] + dungeon[1][0] >= dp[2][0]
            # 1、dp[1][0] >= dp[2][0] - dungeon[1][0]
            # 2、dp[1][0] >= 1
            # dp[1][0] = Math.max( 1,dp[2][0] - dungeon[1][0])

            dp[ i ][ n - 1 ] = max( 1 , dp[ i + 1 ][ n - 1 ] - dungeon[ i ][ n - 1 ])
    


        # 当骑士来到最后一行的时候，他只能向右移动
        for j in range( n - 2 , -1 ,-1 ) : 

            # dp[1][0] + dungeon[1][0] >= dp[2][0]
            # 1、dp[1][0] >= dp[2][0] - dungeon[1][0]
            # 2、dp[1][0] >= 1
            # dp[1][0] = Math.max( 1,dp[2][0] - dungeon[1][0])

            dp[ m - 1][ j ] = max( 1 , dp[ m - 1][ j + 1 ] - dungeon[ m - 1 ][ j ])
    
       
        
        # 从右下角开始向左上角推导
        # 相当于公主救骑士
        for i in range( m - 2 , -1 ,-1 ) : 

            for j in range( n - 2 , -1 ,-1 ) : 
                
                # 当骑士来到 （ i ，j ） 这个位置时，可以选择向右移动，也可以选择向下移动
                # 骑士会选择对血量要求少的那个方向
                mmin = min(dp[ i + 1 ][ j ] , dp[ i ][ j + 1 ])

                # dp[1][0] + dungeon[1][0] >= dp[2][0]
                # 1、dp[1][0] >= dp[2][0] - dungeon[1][0]
                # 2、dp[1][0] >= 1
                # dp[1][0] = Math.max( 1,dp[2][0] - dungeon[1][0])
                dp[i][j] = max( 1 , mmin - dungeon[i][j])


        # dp[0][0] 表示骑士来到第 0 行第 0 列时必须拥有的最小生命值
        return dp[0][0]

← LeetCode 120、三角形最小路径和 LeetCode 718、最长重复子数组 →

# LeetCode 174、地下城游戏

# 一、题目描述

# 二、题目解析

# 三、参考代码

# 1、Java 代码

# 1、Java 代码

# **2、**C++ 代码

# 3、Python 代码

# 2、C++ 代码